class Solution:
    def minOperationsToFlip(self, expression: str) -> int:
        size = len(expression)

        # 状态矩阵：dp[i] = [变成0的花费,变成1的花费] 其中i为括号层级
        mark = ["="]
        dp = [[0, 0]]

        for i in range(size):
            if expression[i] == "(":
                mark.append("=")
                dp.append([0, 0])
            elif expression[i] == ")":
                m0, m1 = dp.pop()
                # 是上层括号等级的第1个数字
                if mark[-1] == "=":
                    dp[-1] = [m0, m1]

                # 不是上层括号等级的第1个数字
                elif mark[-1] == "&":
                    n0, n1 = dp[-1]
                    dp[-1] = [
                        min(n0 + 0 + 0,  # 0与0,0与1 (0或0)
                            0 + 0 + m0),  # 0与0,1与0 (0或0)
                        min(n0 + 1 + m1,  # 0或1
                            n1 + 1 + m0,  # 1或0
                            n1 + 0 + m1)  # 1与1 (1或1)
                    ]

                elif mark[-1] == "|":
                    n0, n1 = dp[-1]
                    dp[-1] = [
                        min(n0 + 0 + m0,  # 0或0
                            n0 + 1 + 0,  # 0与*
                            0 + 1 + m0),  # *与0
                        min(n0 + 0 + m1,  # 0或1
                            n1 + 0 + m1,  # 1或1
                            n1 + 0 + m0,  # 1或0
                            n1 + 1 + m1  # 1与1
                            )
                    ]

                mark.pop()

            elif expression[i] == "0":
                # 当前括号层级的第1个数字
                if mark[-1] == "=":
                    dp[-1] = [0, 1]

                # 当前括号层级不是第1个数字
                elif mark[-1] == "&":  # 与0
                    n0, n1 = dp[-1]
                    dp[-1] = [0, min(n0 + 2, n1 + 1)]

                elif mark[-1] == "|":  # 或0
                    n0, n1 = dp[-1]
                    dp[-1] = [min(n0, n1 + 1), min(n0 + 1, n1)]

                mark.pop()

            elif expression[i] == "1":
                # 当前括号层级的第1个数字
                if mark[-1] == "=":
                    dp[-1] = [1, 0]

                # 当前括号层级不是第1个数字
                elif mark[-1] == "&":
                    n0, n1 = dp[-1]
                    dp[-1] = [min(n0, n1 + 1), min(n0 + 1, n1)]

                elif mark[-1] == "|":
                    n0, n1 = dp[-1]
                    dp[-1] = [min(n0 + 1, n1 + 2), 0]

                mark.pop()

            elif expression[i] == "&":
                mark.append("&")
            elif expression[i] == "|":
                mark.append("|")

        return max(dp.pop())


if __name__ == "__main__":
    print(Solution().minOperationsToFlip("1&(0|1)"))  # 1
    print(Solution().minOperationsToFlip("(0&0)&(0&0&0)"))  # 3
    print(Solution().minOperationsToFlip("(0|(1|0&1))"))  # 1
